package hypergraph;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import parse.Constants;


public class HyperGraph implements Constants{
	
	private HashMap<String,HyperEdge> hlist;
	private Node origin;
	private Node destiny;
	private static int currColor=0;
	private static Set<HyperEdge> touched;
	
	public HyperGraph () {
		hlist = new HashMap<String,HyperEdge> ();
		origin=null;
		destiny=null;
		touched = new HashSet<HyperEdge> ();
	}
	public Node getOrigin() {
		return origin;
	}

	public Node getDestiny() {
		return destiny;
	}

	public void setOrigin(Node origin) {
		this.origin = origin;
	}

	public void setDestiny(Node destiny) {
		this.destiny = destiny;
	}
	
	public boolean add(HyperEdge he) {
		if (he == null) {
			throw new NullPointerException("null hyperedge");
		}
		if( hlist.containsKey(he.getName())){
			return false;
		}
		
		hlist.put(he.getName(), he);
		return true;
	}
	
	public int minPath() {
		HyperEdge haux;
		Node src, dst;
		Set<HyperEdge> min;
		PriorityQueue<HyperEdge> pq;
		
		src = origin;
		dst = destiny;
		
		src.setPrevious(null);
		pq = new PriorityQueue<HyperEdge> ();
		
		/** Por cada hiperarco al que apunta el nod src, se le setea
		 * su minpath a si mismo y se encolan en la priority queue
		 */
		for (HyperEdge h : src.getAdj()) {
			min = new HashSet<HyperEdge>();
			min.add(h);
			h.setMinPath(min);
			pq.offer(h);
		}
		
		/** Mientras la cola no este vacia, continua el algoritmo,
		 * caso contrario no se encontro un camino
		 */
		while (!pq.isEmpty()) {
			haux = pq.poll(); /** Desencola una hiperarista */
			
			/** Por cada nodo cabeza de la hiperarista... */
			for (Node n : haux.getHeads()) {
				/** Si uno de los nodos al que apunta es el destino,
				 * ya se encontro camino minimo
				 */
				if (n.equals(dst)) {
					n.setPrevious(haux);
					this.drawMinPath();
					
					return haux.evaluateWeight();
				}
				
				/** Para cada hiperarisa, apuntada por el nodo n ... */
				for (HyperEdge nEdge : n.getAdj()) {
					/** Si aun no se consiguieron los assets para habilitar la harista ...*/
					if (!nEdge.isOpen()) {
						int npos, nauxpos;
						Set<HyperEdge> s[];
						
						/** Obtiene la posicion del nodo n por el que se llego
						 * a la harista en la lista de nodos cola de la harista a la que apunta n
						 */
						npos = nEdge.getTails().indexOf(n);
						s = nEdge.getPaths();
						
						/** Si aun no habia camino minimo parcial hacia la harista nedge
						 * mediante n, se lo construye con el camino minimo que contenia la harista haux
						 */

						s[npos] = new HashSet<HyperEdge> (haux.getMinPath());
						n.setPrevious(haux);  /** Setea su paso previo al hiperarco haux */
						/** Luego se toman todos los nodos cabeza de haux != n que llegan hacia nEdge */
						
						for (Node naux : haux.getHeads()) {
							if (!naux.equals(n) && nEdge.getTails().contains(naux)) {
								nauxpos = nEdge.getTails().indexOf(naux);
								
								/** A dichos nodos, se le construye dicho camino tambien. Caso contrario, se
								 * le borra su camino previo, y se actualiza.
								 */
								s[nauxpos] = new HashSet<HyperEdge> (haux.getMinPath());
								naux.setPrevious(haux);
							}
						}
						
						/** Si luego de los assets conseguidos recientemente, se habilita
						 * el paso por nEdge, construye el camino minimo final hacia nEdge
						 * y encola dicha hiperarista
						 */
						if (nEdge.isOpen()) {
							nEdge.evaluatePath();
							pq.offer(nEdge);
						}
					}
				}
			}
		}
		return -1;
	}
	
	public void drawMinPath() {

		this.origin.setMinPathMark(true);
		markPath(this.destiny);
	}
	
	private void markPath( Node node ){
		
		if( node.getPrevious()!= null ){
			node.setMinPathMark(true);
			node.getPrevious().setMinPathMark(true);
			for( Node n: node.getPrevious().getTails() ){
				markPath(n);
			}
		}
		
	}

	
	public void CreateHyperGraphDotFile(String fname) throws IOException {
		
		Writer output, minOutput;
		HashMap<String, Node> nmap;
		
		nmap = new HashMap<String, Node> ();
		
		minOutput = new BufferedWriter(new FileWriter(new File( DOT_DIRECTORY + fname + ".min.dot")));
		output = new BufferedWriter(new FileWriter(new File( DOT_DIRECTORY + fname + ".dot")));
		
		minOutput.write("digraph {\n");
		minOutput.write("center =  true;\n");
		output.write("digraph {\n");
		output.write("center =  true;\n");
				
		makeDotFile(minOutput, output, this.origin, nmap);
		
		output.write("}");
		minOutput.write("}");
		
		output.flush();
		output.close();
		minOutput.flush();
		minOutput.close();
		
		return;	
	}
	
	private boolean makeDotFile(Writer minOutput, Writer output, Node src, HashMap<String, Node> nmap) throws IOException {
		for (HyperEdge h : hlist.values()) {
			minOutput.write(h.toDotString() + "\n");
			
			tempChangeMinMark(output, h);
			
			for (Node ntail : h.getTails()) {
				if (!nmap.containsKey(ntail.getName())) {
					nmap.put(ntail.getName(), ntail);
					minOutput.write(ntail.toDotString() + "\n");
					
					tempChangeMinMark(output, ntail);
				}
				
				output.write(ntail.getName() + " -> " + h.getName());
				minOutput.write(ntail.getName() + " -> " + h.getName());
				
				if (h.isMinPathMark() ) {	
					minOutput.write(" [style=bold, color=red];\n");
					output.write(" [color=black];\n");
				} else {
					minOutput.write(" [style=dotted, arrowhead=vee, color=black];\n");
					output.write(" [color=black];\n");
				}
			}
			
			for (Node nhead : h.getHeads()) {
				if (!nmap.containsKey(nhead.getName())) {
					nmap.put(nhead.getName(), nhead);
					minOutput.write(nhead.toDotString() + "\n");
					tempChangeMinMark(output, nhead);
				}
				
				output.write(h.getName() + " -> " + nhead.getName());
				minOutput.write(h.getName() + " -> " + nhead.getName());
				
				if (h.isMinPathMark() /** && nhead.getPrevious().equals(h)*/ && nhead.isMinPathMark()) {	
					minOutput.write(" [style=bold, color=red];\n");
					output.write(" [color=black];\n");
				} else {
					minOutput.write(" [style=dotted, arrowhead=vee, color=black];\n");
					output.write(" [color=black];\n");
					
				}
			}
		}
		return true;
	}
	
	private void tempChangeMinMark(Writer w, HyperEdge h) throws IOException {
		if (h.isMinPathMark()) {
			h.setMinPathMark(false);
			w.write(h.toDotString() + "\n");
			h.setMinPathMark(true);
		} else {
			w.write(h.toDotString() + "\n");
		}
	}
	
	private void tempChangeMinMark(Writer w, Node n) throws IOException {
		if (n.isMinPathMark()) {
			n.setMinPathMark(false);
			w.write(n.toDotString() + "\n");
			n.setMinPathMark(true);
		} else {
			w.write(n.toDotString() + "\n");
		}
	}
	
	public void CreateMinHgFile(String name) throws IOException {
		final String minName = name + ".min.hg";
		String minNodes;
		Writer output;
		List<Node> nlist;
		
		output = new BufferedWriter(new FileWriter(new File( HG_DIRECTORY + minName)));
		
		output.write(origin.toString()+ "\n");
		output.write(destiny.toString() + "\n");
		
		for (HyperEdge h : hlist.values()) {
			if (h.isMinPathMark()) {
				output.write(h.toString() + " ");
				output.write(h.getWeight() + " ");
				nlist = h.getHeads();
				minNodes = getMinNodes(nlist);
				output.write(nlist.size() + " ");
				output.write(minNodes);
				
				nlist = h.getTails();
				minNodes = getMinNodes(nlist);
				output.write(nlist.size() + " ");
				output.write(minNodes + "\n");
			}
		}
		output.flush();
		output.close();
	}
	
	private String getMinNodes(List<Node> nlist) {
		String minNodes = "";
		
		for (int i = 0 ; i < nlist.size() ; i++) {
			if (nlist.get(i).isMinPathMark()) {
				minNodes = minNodes.concat(nlist.get(i).toString());
				minNodes = minNodes.concat(" ");
			} else {
				nlist.remove(i);
				--i;
			}
		}
		
		return minNodes;
	}
	
	public void revert() {
		
		HashMap<String,Node> nodes = new HashMap<String,Node>();

		for (HyperEdge ha: this.hlist.values() ){
			ha.revertAndClear();
			
			for( Node node: ha.getHeads()){
				if( !nodes.containsKey( node.getName()) ){
					nodes.put(node.getName(), node);
					node.clearForRevert();				
				}
			}
			for( Node node: ha.getTails()){
				if( !nodes.containsKey( node.getName()) ){
					nodes.put(node.getName(), node);
					node.clearForRevert();
				}
				node.getAdj().add( ha );
			}
		}
	}

	public int getMinPath(int limit) {
		int tempWeight;
		Set<HyperEdge> hset;
		
		/* hset guarda conjuntos de un unico elemento (adyacentes del nodo TARGET) */
		hset = new HashSet<HyperEdge> ();
		tempWeight = 0;
		
		/* Por cada hiperarco apuntado por destino, en cada iteracion
		 * agrega dicho hiperarco al conjunto, y llama a la funcion que recorre todos
		 * los caminos posibles hacia la solucion
		 */
		long time = System.currentTimeMillis();
		
		for (HyperEdge ha : this.destiny.getAdj()) {
			hset.add(ha);
			
			if (ha.getWeight() < limit) { // Podria ocurrir que ya el primer arco se pase
				
				tempWeight = doMinPath(hset, limit, ha.getWeight());
				
				if( tempWeight < limit ){
					limit= tempWeight;
					ha.paint( currColor );
				}
				
				hset.clear();
			}
		}
		
		time = System.currentTimeMillis() - time;
		
		int seg = (int)(time/1000);
		int resto = (int)(time%1000);
		System.out.println( "Tiempo Procesamiento: " + seg + "." + resto + " seg");
		
				
		markMinPath( destiny );
		
		return tempWeight;
	}
	
	private void markMinPath( Node node ){
	
//		System.out.println( node );
		node.setMinPathMark( true );
		
		for( HyperEdge ha: node.getAdj() ){
			if( ha.getColor() != 0 ){
//				System.out.println( ha + " con color: " + ha.getColor() + " x:" + currColor );
			}
			if( ha.getColor() == currColor ){
				ha.setMinPathMark( true );
				for( Node n: ha.getHeads() ){
					markMinPath( n );
				}
			}
		}
	}
	
	private int doMinPath(Set<HyperEdge> pathSets, int limit, int acum) {
		List<Set<HyperEdge>> possiblePaths;
		int tempWeight;
		
		/* Dado un conjunto de nodos, construye todo las posibles caminos por donde
		 * cotinuar
		 */
		
		possiblePaths = buildPaths(pathSets);
//		System.out.println( "p: "+ pathSets );
//		System.out.println( possiblePaths );
		
		if( possiblePaths.isEmpty() ){
				currColor++;
				paint( pathSets );
//				System.out.println( "pinta: " + currColor + pathSets );
				return acum;
		}
		/* Luego por cada una de esas opciones, la evalua siempre y cuando el peso de esa
		 * opcion + el acumulado hasta el momento no supere la cota dada por limit
		 */
		for (Set<HyperEdge> hset : possiblePaths) {
			tempWeight = HyperEdge.getSetWeight(hset) + acum;
			
			if (tempWeight < limit) {
				/* Los hiperarcos del posible camino son marcados, pues podria ocurrir el caso h1 -> n1 -> h3
				 * y h2 -> n2 -> h1, con lo cual repetiria combinaciones innecesarias ademas de sumar acumulados
				 * incorrectos
				 */
				for (HyperEdge h : hset) {
					if (!h.isTouched()) {
						touched.add(h);
						h.setTouched(true);
					}
				}
				
				
				/* Si llego a SOURCE con mejor peso que la cota, actualiza la cota */
				tempWeight = doMinPath(hset, limit, tempWeight);
				
				/* desmarca los hiperarcos del camino recien testeados */
				for (HyperEdge h : touched) {
					h.setTouched(false);
				}
				touched.clear();
				
				if ( tempWeight < limit) {
					limit = tempWeight;
					paint( pathSets );
				}
			}
			
		}
		return limit;
	}

	private void paint( Set<HyperEdge> hes){
		for( HyperEdge h: hes ){
			h.paint( currColor );
		}
	}
	
	private List<Set<HyperEdge>> buildPaths( Set<HyperEdge> cBase ){
		
		if( cBase == null || cBase.isEmpty() ){
			throw new IllegalArgumentException();
		}
		List<Set<HyperEdge>> options = new LinkedList<Set<HyperEdge>>();
		
		List<Set<HyperEdge>> combinations = prepare(cBase);
		
		while( !combinations.isEmpty() ){
			options.add( combinations.remove(0) );
		}
		
		return options;
	}
	
	private List<Set<HyperEdge>> prepare( Set<HyperEdge> cBase ){
		int discard;
		List<Integer> index = new ArrayList<Integer>();
		List<Integer> op = new ArrayList<Integer>();
		List<List<HyperEdge>> harray = new LinkedList<List<HyperEdge>>();
		List<Set<HyperEdge>> options = new LinkedList<Set<HyperEdge>>();
		
		for( HyperEdge ha: cBase ){
			for( Node n: ha.getHeads() ){
				discard = 0;
				List<HyperEdge> setOp = new LinkedList<HyperEdge>(); // opciones
				
				for( HyperEdge h: n.getAdj() ){
					if (!h.isTouched()) { // si el hiperarco no se encuentra ya marcado, lo agrega a la combinatoria
						setOp.add( h );
					} else {
						discard++; // Para que no sea "contado" en index 
					}
				}
				if( n.getAdj().size() !=0 ){ // Si llega a source harray queda vacio 
					if (!setOp.isEmpty()) { // pudo haber ocurrido que setOp quedo vacio ya que todos los hiperarcos estaban marcados
						harray.add( setOp );
						index.add( n.getAdj().size() - 1 - discard);
						op.add( 0 ); // initialValue index
					}
				}
			}
		}
		if( harray.isEmpty()){
			return options; // conjunto vacio
		}
		do{ 
			// en op tengo los indices de la nueva opcion inicializado en (0,0,0,... )
			Set<HyperEdge> mySet = new HashSet<HyperEdge>();
			
			int j=0;
//			try {
			for( int o: op ){
//				System.out.println("harray tam: " + harray.size() + " op tam: " + op.size());
				mySet.add( harray.get(j++).get(o) );
			}
//			} catch (IndexOutOfBoundsException ie) {
//				System.out.println(harray.toString() + op.toString());
//			}
			options.add( mySet );
//			System.out.println( mySet );
			
		} while( combineIndex( index, op ) );
		
		return options;
	}

	private boolean combineIndex( List<Integer> haSize, List<Integer> op ){
		
		for( int i = op.size()-1 ; i>=0; i-- ){
			if( ( op.get(i) + 1 ) > haSize.get(i) ){
				op.set(i, 0);
			} else {
				op.set(i, op.get(i) + 1 );
				break;
			}
		}
		for( Integer i: op ){
			if( i != 0 ){
				return true;
			}
		}
		return false;
	}

	
}